home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group01b.txt / 000041_icon-group-sender_Thu Mar 1 08:43:25 2001.msg < prev    next >
Internet Message Format  |  2002-01-03  |  3KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id f21FhLc22736
  4.     for icon-group-addresses; Thu, 1 Mar 2001 08:43:21 -0700 (MST)
  5. Message-Id: <200103011543.f21FhLc22736@baskerville.CS.Arizona.EDU>
  6. Date: Thu, 01 Mar 2001 09:59:23 -0500
  7. From: "Steve Graham" <Steve_Graham@labcorp.com>
  8. To: <icon-group@cs.arizona.edu>, <cary@cup.hp.com>
  9. Subject: Re: New Scientist puzzle
  10. Content-Disposition: inline
  11. X-MIME-Autoconverted: from quoted-printable to 8bit by baskerville.CS.Arizona.EDU id f21Exu821117
  12. Errors-To: icon-group-errors@cs.arizona.edu
  13. Status: RO
  14. Content-Length: 2038
  15.  
  16. Cary,
  17.  
  18.    Nice, compact, understandable solution.
  19.  
  20.  
  21. Steve
  22.  
  23. >>> Cary Coutant <cary@cup.hp.com> 02/28/01 06:05PM >>>
  24. My solution recognizes that map() can do most of the work for you:
  25.  
  26. map("62419409", "62419409", "VIERNEUN") == "VIERNEUN"
  27. map("VIERNEUN", "VIERNEUN", "62419409") == "62419409"
  28.  
  29. These two tests verify that each letter is used, and that each digit maps 
  30. to a different letter.
  31.  
  32. I then made a list of candidate solutions that satisfy the first 
  33. condition, and used two tables to cross-reference the numbers to find the 
  34. solution(s) where one number uniquely determines the other.
  35.  
  36. Interestingly, the puzzle works in English with one minor change. "FOUR 
  37. NINE" doesn't have a solution, but "FIVE NINE" does.
  38.  
  39. -cary
  40.  
  41.  
  42. procedure main(args)
  43.     local pat1, pat2, pats
  44.     local t1, t2, solutions
  45.     local num1, num2, nums
  46.     local soln
  47.  
  48.     # Get patterns from the command line
  49.  
  50.     pat1 := args[1] | "VIER"
  51.     pat2 := args[2] | "NEUN"
  52.     pats := pat1 || pat2
  53.  
  54.     # Initialize cross-reference tables
  55.     # and list of solutions
  56.  
  57.     t1 := table(0)      # t1[n] counts solutions of form (n,x)
  58.     t2 := table(0)      # t2[n] counts solutions of form (x,n)
  59.     solutions := []
  60.  
  61.     # Generate all possible solutions and check against patterns
  62.  
  63.     every num1 := gen_squares(*pat1) &
  64.             num2 := gen_squares(*pat2) do {
  65.         nums := num1 || num2
  66.         if map(pats, pats, nums) == nums &
  67.                 map(nums, nums, pats) == pats then {
  68.             t1[num1] +:= 1
  69.             t2[num2] +:= 1
  70.             put(solutions, [num1, num2])
  71.             }
  72.         }
  73.  
  74.     # Look for solutions where each number
  75.     # uniquely determines the other
  76.  
  77.     while soln := get(solutions) do
  78.         if t1[soln[1]] = t2[soln[2]] = 1 then
  79.             write(soln[1], " ", soln[2])
  80.  
  81. end
  82.  
  83.  
  84. # Generate squares of given length
  85.  
  86. procedure gen_squares(len)
  87.     local n, inc
  88.  
  89.     n := 1
  90.     inc := 3
  91.     repeat {
  92.         if *n > len then fail
  93.         if *n = len then suspend string(n)
  94.         n +:= inc
  95.         inc +:= 2
  96.         }
  97.  
  98. end
  99.  
  100.  
  101.